package com.example.demo.tixiban;

/**
 * @author xujm
 * @version V2.4
 * @since 2.4.0 2022/2/20 11:41
 */
public class Arr_一个数组中两个数出现奇数次其他出现偶数次 {

    /**
     * 思路:
     *   (1)偶数次的数 异或后 结果为0
     *   (2)奇数次的数 异或后 不重复的位上存在1
     *   举例:  奇数个a=1100  奇数个b=0011   异或后 存在 1111
     *   那么整个数组异或 eor == a ^ b == 1111
     *   取最右侧的那个1  rightOne == eor &(~eor+1)
     *   那么可以筛选出一堆偶数次得数和 b或者a
     *   (3) 整个数组再次异或 条件: 最右边存在leftone。
     *   eor2 ==  a或者b 异或上一堆偶数
     *   (4)
     *   讨论:
     *   eor2 == a 或者 b
     *   4.1 eor 异或 eor2 == a ^ b  ^ b == a
     *   4.2 eor 异或 eor2 == a ^ b  ^ a == b
     *
     *
     *
     * @param arr
     */
    public static void find(int [] arr){
        int eor = 0;
        for(int i =0;i<arr.length;i++){
            eor = eor ^ arr[i];
        }
        int rightOne = eor &(~eor+1);
        int eor2 = 0;
        for(int i =0;i<arr.length;i++){
            if((arr[i] & rightOne) > 0){
                eor2 = eor2 ^ arr[i];
            }
        }
        int other = eor ^ eor2;
        System.out.println(eor2);
        System.out.println(other);
    }


    public static void main(String[] args) {
        int [] arr ={4,11,2,2,3,3,15,15,15,15};
        find(arr);
    }

}
